Settings

Some settings for better notebook rendering

Mathjax Extensions

\require{cancel}

$$ \require{cancel} $$

Latex shortcuts

$$
\newcommand{\n}{\neg}
\newcommand{\v}{\vee}
\newcommand{\bv}{\bigvee}
\newcommand{\w}{\wedge}
\newcommand{\bw}{\bigwedge}
\newcommand{\i}{\implies}
\newcommand{\c}{\cancel}
$$

$$ \newcommand{\n}{\neg} \newcommand{\v}{\vee} \newcommand{\bv}{\bigvee} \newcommand{\w}{\wedge} \newcommand{\bw}{\bigwedge} \newcommand{\i}{\implies} \newcommand{\c}{\cancel} $$

Why logic?

Inference has 2 parts

• Soundness (only valid conclusions can be proven)
• Completeness (all valid conclusions can be proven)

Predicates

A function that maps object arguments to true or false

If Feathers(animal):
    Then Bird(animal)

Conjunction (logical AND)

If an animal lays eggse and it flies, then its a bird

If Lays-Eggs(animal) ^ Flies(animal): 
    Then Bird(animal)

Disjunction (logical OR)

If an animal lays eggs ir it flies then its a bird

If Lays-Eggs(animal) V Flies(animal):
    Then Bird(animal)

Practice

If an animal lays eggs and its not a bird, then its a bat

If Lays-Eggs(animal) ^ !Bird(animal):
    Then Bat(animal)

Alternate Notations

Truth Tables II

def get_truth(A, B, C):
    return A or (B and not C)

get_truth(True, True, True)

True

get_truth(True, True, False)

True

get_truth(True, False, True)

True

get_truth(True, False, False)

True

get_truth(False, True, True)

False

get_truth(False, True, False)

True

get_truth(False, False, True)

False

get_truth(False, False, False)

False

Properties

• Commutative: A & B = B & A
• Commutative: A | B = B | A
• Distributive: A & (B | C) = (A & B) | (A & C)
• Distributive: A | (B & C) = (A | B) & (A | C)
• Associative: A | (B | C) = (A | B) | C
• Associative: A & (B & C) = (A & B) & C
• De Morgan's Law: !(A and B) = !A | !B
• De Morgan's Law: !(A | B) = !A & !B

Associative works when all operators are same. Distributive works when there is a mixture.

Truth of Implications (tricky, read carefully)

Sentences may contain implications.

A	B	A => B	Example
True	True	True	Bluebird has feather thus its a bird
True	False	False	Fish has scales but its not a bird
False	True	True	Penguin does not have feather, but its a bird
False	False	False	Cat does not have feather thus its not a bird

Implication Elimination

It is better to convert Implication to alternate equivalent.

A	B	!A \	B
True	True	True
True	False	False
False	True	True
False	False	True

In single sentence, either animal does not have feathers or its a bird

Rules of Inference

Modus Ponens

• Robot is fed with knowledge: Feathers => Birds
• Robot sees Feathers in an animal
• Robot inferences it as Bird

Modus Tollens

• Robot is fed with knowledge: Feathers => Birds
• Robot sees an animal is not bird
• Robot inferences it does not have feather

Not feasible

What we saw so far are not feasbile for complex tasks.

Quantifiers

Instead of specifying for every animal possible, we could quantify and represent as below.

All animals (Universal Quantifiers)

Some Animals (Existential Quantifiers)

Normal Forms

Ref

Remember, we call OR as disjunction and AND as conjunction, but what if we have more such relations in sentences?

Clauses

Clause	Result	Example

Clause contains only $\wedge$ | conjunctive clause | $$p \wedge \neg q \wedge r $$ Clause contains only $\vee$ | disjunctive clause | $$p \vee \neg q \vee r $$ Clause containing both | neither | $$p \vee \neg q \wedge r $$

Conjunctive Normal Form

• Combining disjunctive clauses together with $\bigwedge$
• It is an AND of ORs
• Example: $(p \vee q) \wedge (q \vee \neg r)$

Exercise

Example	CNF?	Reason
$$(A \v B) \w (A \v C)$$	yes	Disjunctive clauses combined with conjunction
$$A \v B \v C$$	yes	Its a pure disjunctive clause, so its a CNF
$$B \v C$$	yes	A disjuctive clause is a CNF
$$\n B \v C$$	yes	A disjuctive clause is a CNF
$$B$$	yes	A literal is both CNF and DNF
$$\n (B \v C)$$	No	This is neither a disjuctive clause nor literal
$$(A \w B) \v C$$	No	Disjunctive clauses combined via $\v$

Disjunctive Normal Form

• Combining conjunctive clauses together with $\bigvee$
• It is an OR of ANDs
• Example: $(p \wedge q) \vee (q \wedge \neg r)$

Example	DNF?	Reason
$$(A \w B) \v (A \w C)$$	yes	Conjuctive clauses combined with disjuction
$$A \w B \w C$$	yes	Its a pure conjunctive clause, so its a DNF
$$B \w C$$	yes	A conjunctive clause is a DNF
$$\n B \w C$$	yes	A conjunctive clause is a DNF
$$B$$	yes	A literal is both CNF and DNF
$$\n (B \w C)$$	No	This is neither a conjunctive clause nor literal
$$(A \v B) \w C$$	No	Conjunctive clauses combined via $\w$

Resolution Theorem Proving ( A Simple Proof )

General Knowledge: S1: !can-move => !liftable (Robot's general knowledge)
A Percept: S2: !can-move (Robert perceives an object not moveable)
Inference: S3: !liftable (Modus Ponens)

Via RTP method:

• convert each sentence to conjunctive normal form
• S1 is not in conjunctive normal form, so Implication Elimination Rule helps here to convert to CNF

!can-move => !liftable becomes !(!can-move) V !liftable which again becomes !can-move V !liftable which is a CNF

• S2 is already in CNF.
• Take S3 as opposite of what to prove. Robot wants to prove object is not liftable so S3 becomes S3: liftable

Summarizing

S1: can-move V !liftable
S2: !can-move
S3: liftable

• Look for sentence that contains negation of S3. Here that is S1
• Both S3 and its negation in S1 cannot co exist so we eliminate them.
• Now for can-move in S1, the negation in S2, and both cannot co exist so we remove them too.

A complex proof

Input

S1: $\n$ can-move $\bw$ battery-full $\i$ $\n$ liftable
S2: $\n$ can-move
S3: battery-full

Implication Elimination of S1

Recall $a \i b$ could be written as $\n a \bv b$

Setting a = ($\n$ can-move $\bw$ battery-full ), we get S1 as

S1: $\n$ ($\n$ can-move $\bw$ battery-full) $\bv$ liftable

Is S1 in CNF?

Converting to a simple form,

S1: $\n(\n A \w B) \v C$

Here, $\n(\n A \w B)$ is not even a conjunctive or disjunctive clause. So its not a CNF.

De-morgan's law

De morgan's law states that

$\n(A \w B) = \n A \v \n B$

Therefore,

$\n(\n A \w B) = \n \n A \v \n B = A \v \n B$

Thus,

S1: (can-move $\bv$ $\n$ battery-full) $\bv$ liftable

Is S1 in CNF?

Converint to a simple form

S1: $A \bv B \bv C$

Its a disjuctive clause (clause containing only disjunctions), so its a CNF!

RTP

Now introduce the 4th sentence, which should be negatiion of what to prove

We want to prove, not liftable. So,

S4: liftable

Summarizing, let A = can-move, B = liftable, C = battery-full, then

$$ S1: A \bv \n B \bv \n C \\ S2: \n A \\ S3: C \\ S4: B $$

Step 1

$$ S1: A \bv \c{\n B} \bv \n C \\ S2: \n A \\ S3: C \\ S4: \c{B} $$

Step 2

$$ S1: \c{A} \bv \c{\n B} \bv \n C \\ S2: \c{\n A} \\ S3: C \\ S4: \c{B} $$

Step 3

$$ S1: \c{A} \bv \c{\n B} \bv \c{\n C} \\ S2: \c{\n A} \\ S3: \c{C} \\ S4: \c{B} $$

Why this works?

Because of Horn Clause which contains atmost one positive literal. Note S1.

Exercise: Proof 1

If an animal has wings and does not have fur, it is a bird

Answer:

has-wings(animal) & !has-fur(animal) => bird(animal)

Exercise: Proof II

Implication Elimination

Recall $a \i b$ could be written as $\n a \bv b$

Setting A = has-wings, B = has-fur, C = bird, we get

S1 : $(A \w \n B) \i C$

That becomes

$$ S1: \n (A \w \n B) \v C $$

In textual form and including C

S1: !(has-wings & !has-fur) | bird

Exercise: Proof III

De morgan's law

$$ \n(A \w B) = \n A \v \n B $$

Therefore

$$ \n(A \w \n B) = \n A \v \n\n B = \n A \v B $$

In textual form and including C

!has-wings | has-fur | bird

Exercise: RTP

$$ S1: \n A \v B \v C \\ S2: A \\ S3: \n B \\ S4: \n C $$

$$ S1: \n A \v B \v \c{C} \\ S2: A \\ S3: \n B \\ S4: \c{\n C} $$

$$ S1: \c{\n A} \v B \v \c{C} \\ S2: \c{A} \\ S3: \n B \\ S4: \c{\n C} $$

$$ S1: \c{\n A} \c{\v B} \v \c{C} \\ S2: \c{A} \\ S3: \c{\n B} \\ S4: \c{\n C} $$

Cognitive Connection

Abduction is reasoning from effects to causes
Deduction is reasoning from causes to effects
Induction is given cause-effect relation from sample, deduce for population